#include "pch.h"

TwoDistanceEngine::TwoDistanceEngine(const Board & board) : board(board)
{
	this->size = board.s();
	calc_left_down_right_up_raw();
	calc_left_up_right_down_raw();
}

void TwoDistanceEngine::two_dis(Graph & g, int s, int * out)
{
	int dis[ARR_SIZE + 5];
	int subdis[ARR_SIZE + 5];
	int twodis[ARR_SIZE + 5];
	bool vis[ARR_SIZE + 5];
	//const int INF = 0x3f3f3f3f;

	memset(dis, INF, sizeof(dis));
	memset(subdis, INF, sizeof(subdis));
	memset(twodis, INF, sizeof(twodis));
	memset(vis, 0, sizeof(vis));

	dis[s] = 0;
	subdis[s] = 0;
	twodis[s] = 0;

	std::queue<int> q;
	vis[s] = true;
	q.push(s);
	for (int e = g.head[s]; e != -1; e = g.edge[e].next)
	{
		int to = g.edge[e].to;
		subdis[to] = 0;
		dis[to] = 0;
		twodis[to] = 1;
		q.push(to);
		vis[to] = true;
	}

	while (!q.empty())
	{
		int p = q.front();
		q.pop();

		vis[p] = false;
		for (int e = g.head[p]; e != -1; e = g.edge[e].next)
		{
			int to = g.edge[e].to;
			int d = twodis[p];
			bool flag = false;
			if (d < dis[to])
			{
				subdis[to] = dis[to];
				dis[to] = d;
				twodis[to] = subdis[to] + 1;
				flag = true;
			}
			else if (d < subdis[to])
			{
				subdis[to] = d;
				twodis[to] = d + 1;
				flag = true;
			}
			if (flag && vis[to] == false)
			{
				q.push(to);
				vis[to] = true;
			}
		}
	}

	for (int i = 0; i < size * size; i++)
	{
		out[i] = twodis[i];
	}
}

// blue
void TwoDistanceEngine::left_down(int * out)
{
	bool vis[20][20];
	std::queue<int> q;

	Graph g = left_down_right_up_raw;

	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < size; i++)
	{
		if (board.get(i, 0) == 0)
		{
			add(g, size * size, i * size);
			add(g, i * size, size * size);
			vis[i][0] = true;
		}
		else if (board.get(i, 0) == 2)
		{
			q.push(i * size);
			vis[i][0] = true;
		}
	}
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		int x = p / size;
		int y = p % size;
		for (int i = 0; i < 6; i++)
		{
			int nx = x + u[i];
			int ny = y + v[i];
			if (nx >= 0 && nx < size && ny >= 0 && ny < size)
			{
				int npos = nx * size + ny;
				if (board.get(nx, ny) == 0)
				{
					if (vis[nx][ny] == false)
					{
						// adjacent
						add(g,  size * size, npos);
						add(g, npos,  size * size);
						vis[nx][ny] = true;
					}
				}
				else if (board.get(nx, ny) == 2)
				{
					if (vis[nx][ny] == false)
					{
						q.push(npos);
						vis[nx][ny] = true;
					}
				}
			}
		}
	}

	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			if (i != j && board.get(size * i +  size - 1) == 0 && board.get(size * j +  size - 1) == 0)
			{
				add(g, i * size +  size - 1, j * size +  size - 1);
			}
		}
	}

	two_dis(g, size * size, out);
}

void TwoDistanceEngine::right_up(int * out)
{
	bool vis[20][20];
	std::queue<int> q;

	Graph g = left_down_right_up_raw;

	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < size; i++)
	{
		if (board.get(i,  size - 1) == 0)
		{
			add(g,  size * size, i * size +  size - 1);
			add(g, i * size +  size - 1,  size * size);
			vis[i][ size - 1] = true;
		}
		else if (board.get(i,  size - 1) == 2)
		{
			q.push(i * size +  size - 1);
			vis[i][ size - 1] = true;
		}
	}
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		int x = p / size;
		int y = p % size;
		for (int i = 0; i < 6; i++)
		{
			int nx = x + u[i];
			int ny = y + v[i];
			if (nx >= 0 && nx < size && ny >= 0 && ny < size)
			{
				int npos = nx * size + ny;
				if (board.get(nx, ny) == 0)
				{
					if (vis[nx][ny] == false)
					{
						// adjacent
						add(g,  size * size, npos);
						add(g, npos,  size * size);
						vis[nx][ny] = true;
					}
				}
				else if (board.get(nx, ny) == 2)
				{
					if (vis[nx][ny] == false)
					{
						q.push(npos);
						vis[nx][ny] = true;
					}
				}
			}
		}
	}

	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			if (i != j && board.get(size * i) == 0 && board.get(size * j) == 0)
			{
				add(g, i * size, j * size);
			}
		}
	}

	two_dis(g, size * size, out);
}

void TwoDistanceEngine::left_up(int * out)
{
	bool vis[20][20];
	std::queue<int> q;

	Graph g = left_up_right_down_raw;

	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < size; i++)
	{
		if (board.get(0, i) == 0)
		{
			add(g,  size * size, i);
			add(g, i,  size * size);
			vis[0][i] = true;
		}
		else if (board.get(0, i) == 1)
		{
			q.push(i);
			vis[0][i] = true;
		}
	}
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		int x = p / size;
		int y = p % size;
		for (int i = 0; i < 6; i++)
		{
			int nx = x + u[i];
			int ny = y + v[i];
			if (nx >= 0 && nx < size && ny >= 0 && ny < size)
			{
				int npos = nx * size + ny;
				if (board.get(nx, ny) == 0)
				{
					if (vis[nx][ny] == false)
					{
						// adjacent
						add(g,  size * size, npos);
						add(g, npos,  size * size);
						vis[nx][ny] = true;
					}
				}
				else if (board.get(nx, ny) == 1)
				{
					if (vis[nx][ny] == false)
					{
						q.push(npos);
						vis[nx][ny] = true;
					}
				}
			}
		}
	}

	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			if (i != j && board.get(size * (size - 1) + i) == 0 && board.get(size * (size - 1) + j) == 0)
			{
				add(g, size * (size - 1) + i, size * (size - 1) + j);
			}
		}
	}

	two_dis(g, size * size, out);
}

void TwoDistanceEngine::right_down(int * out)
{
	bool vis[20][20];
	std::queue<int> q;

	Graph g = left_up_right_down_raw;

	memset(vis, 0, sizeof(vis));
	for (int i = 0; i < size; i++)
	{
		if (board.get( size - 1, i) == 0)
		{
			add(g, size * size, size * (size - 1) + i);
			add(g, size * (size - 1) + i, size * size);
			vis[ size - 1][i] = true;
		}
		else if (board.get( size - 1, i) == 1)
		{
			q.push(size * (size - 1) + i);
			vis[size - 1][i] = true;
		}
	}
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		int x = p / size;
		int y = p % size;
		for (int i = 0; i < 6; i++)
		{
			int nx = x + u[i];
			int ny = y + v[i];
			if (nx >= 0 && nx < size && ny >= 0 && ny < size)
			{
				int npos = nx * size + ny;
				if (board.get(nx, ny) == 0)
				{
					if (vis[nx][ny] == false)
					{
						// adjacent
						add(g,  size * size, npos);
						add(g, npos,  size * size);
						vis[nx][ny] = true;
					}
				}
				else if (board.get(nx, ny) == 1)
				{
					if (vis[nx][ny] == false)
					{
						q.push(npos);
						vis[nx][ny] = true;
					}
				}
			}
		}
	}

	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			if (i != j && board.get(i) == 0 && board.get(j) == 0)
			{
				add(g, i, j);
			}
		}
	}

	two_dis(g, size * size, out);
}

void TwoDistanceEngine::calc_left_down_right_up_raw()
{
	memset(left_down_right_up_raw.head, -1, sizeof(left_down_right_up_raw.head));
	memset(left_down_right_up_raw.edge, -1, sizeof(left_down_right_up_raw.edge));
	left_down_right_up_raw.edgeNum = 0;

	std::queue<int> q;
	bool vis[20][20];
	for (int i = 0; i < size * size; i++)
	{
		if (board.get(i) != 0)
			continue;

		memset(vis, 0, sizeof(vis));
		q.push(i);
		vis[i / size][i % size] = true;
		while (!q.empty())
		{
			int p = q.front();
			q.pop();
			int x = p / size;
			int y = p % size;
			for (int j = 0; j < 6; j++)
			{
				int nx = x + u[j];
				int ny = y + v[j];

				if (nx >= 0 && nx < size && ny >= 0 && ny < size)
				{
					int npos = nx * size + ny;
					if (board.get(nx, ny) == 0)
					{
						if (vis[nx][ny] == false)
						{
							// adjacent
							add(left_down_right_up_raw, i, npos);
							vis[nx][ny] = true;
						}

					}
					else if (board.get(nx, ny) == 2)
					{
						if (vis[nx][ny] == false)
						{
							q.push(npos);
							vis[nx][ny] = true;
						}

					}
				}
			}
		}
	}
}

void TwoDistanceEngine::calc_left_up_right_down_raw()
{
	memset(left_up_right_down_raw.head, -1, sizeof(left_up_right_down_raw.head));
	memset(left_up_right_down_raw.edge, -1, sizeof(left_up_right_down_raw.edge));
	left_up_right_down_raw.edgeNum = 0;

	std::queue<int> q;
	bool vis[20][20];
	for (int i = 0; i < size * size; i++)
	{
		if (board.get(i) != 0)
			continue;

		memset(vis, 0, sizeof(vis));
		q.push(i);
		vis[i / size][i % size] = true;
		while (!q.empty())
		{
			int p = q.front();
			q.pop();
			int x = p / size;
			int y = p % size;
			for (int j = 0; j < 6; j++)
			{
				int nx = x + u[j];
				int ny = y + v[j];

				if (nx >= 0 && nx < size && ny >= 0 && ny < size)
				{
					int npos = nx * size + ny;
					if (board.get(nx, ny) == 0)
					{
						if (vis[nx][ny] == false)
						{
							// adjacent
							add(left_up_right_down_raw, i, npos);
							vis[nx][ny] = true;
						}

					}
					else if (board.get(nx, ny) == 1)
					{
						if (vis[nx][ny] == false)
						{
							q.push(npos);
							vis[nx][ny] = true;
						}

					}
				}
			}
		}
	}
}